package sword_offer;

import common.ListNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName _06reversePrintListNode
 * @Description: 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：head = [1,3,2]
 * 输出：[2,3,1]
 *  
 *
 * 限制：
 *
 * 0 <= 链表长度 <= 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/13 11:01
 */
public class _06reversePrintListNode {

    public int[] reversePrint(ListNode head) {
        Deque<Integer> deque = new LinkedList<>();
        ListNode cursor = head;
        while (cursor != null){
            deque.addFirst(cursor.val);
            cursor = cursor.next;
        }

        int[] result = new int[deque.size()];
        int length = deque.size();
        for (int i = 0; i < length; i++) {
            result[i] = deque.removeFirst();
        }
        return result;
    }

    private int count = 0;

    public int[] reversePrintImprove(ListNode head) {
        if (head == null){
            return new int[]{};
        }
        ListNode listNode = reverseListNode(head);
        ListNode cursor = listNode;

        int[] result = new int[count];
        for (int i = 0; i < count; i++) {
            result[i] = cursor.val;
            cursor = cursor.next;
        }
        head = reverseListNode(head);
        return result;
    }

    public ListNode reverseListNode(ListNode head){
        ListNode cursor = null;
        while (head != null){
            count++;
            ListNode temp = head.next;

            head.next = cursor;
            cursor = head;

            head = temp;
        }

        return cursor;
    }
}
